home *** CD-ROM | disk | FTP | other *** search
/ The Arsenal Files 8 / The Arsenal Files Collection #8 (Arsenal Computer) (1996).ISO / prg_casm / snip9611.zip / RG_QSORT.C < prev    next >
C/C++ Source or Header  |  1996-11-24  |  7KB  |  154 lines
  1. /* +++Date last modified: 02-Nov-1995 */
  2.  
  3. /******************************************************************/
  4. /* qsort.c  --  Non-Recursive ANSI Quicksort function             */
  5. /*                                                                */
  6. /* Public domain by Raymond Gardner, Englewood CO  February 1991  */
  7. /*                                                                */
  8. /* Usage:                                                         */
  9. /*     qsort(base, nbr_elements, width_bytes, compare_function);  */
  10. /*        void *base;                                             */
  11. /*        size_t nbr_elements, width_bytes;                       */
  12. /*        int (*compare_function)(const void *, const void *);    */
  13. /*                                                                */
  14. /* Sorts an array starting at base, of length nbr_elements, each  */
  15. /* element of size width_bytes, ordered via compare_function,     */
  16. /* which is called as  (*compare_function)(ptr_to_element1,       */
  17. /* ptr_to_element2) and returns < 0 if element1 < element2,       */
  18. /* 0 if element1 = element2, > 0 if element1 > element2.          */
  19. /* Most refinements are due to R. Sedgewick. See "Implementing    */
  20. /* Quicksort Programs", Comm. ACM, Oct. 1978, and Corrigendum,    */
  21. /* Comm. ACM, June 1979.                                          */
  22. /******************************************************************/
  23.  
  24. #include <stddef.h>                     /* for size_t definition  */
  25. #include "snipsort.h"
  26.  
  27. /* prototypes */
  28. void qsort(void *, size_t, size_t,
  29.                            int (*)(const void *, const void *));
  30. void swap_chars(char *, char *, size_t);
  31.  
  32. /*
  33. ** Compile with -DSWAP_INTS if your machine can access an int at an
  34. ** arbitrary location with reasonable efficiency.  (Some machines
  35. ** cannot access an int at an odd address at all, so be careful.)
  36. */
  37.  
  38. #ifdef   SWAP_INTS
  39.  void swap_ints(char *, char *, size_t);
  40.  #define  SWAP(a, b)  (swap_func((char *)(a), (char *)(b), width))
  41. #else
  42.  #define  SWAP(a, b)  (swap_chars((char *)(a), (char *)(b), size))
  43. #endif
  44.  
  45. #define  COMP(a, b)  ((*comp)((void *)(a), (void *)(b)))
  46.  
  47. #define  T           7    /* subfiles of T or fewer elements will */
  48.                           /* be sorted by a simple insertion sort */
  49.                           /* Note!  T must be at least 3          */
  50.  
  51. void qsort(void *basep, size_t nelems, size_t size,
  52.                             int (*comp)(const void *, const void *))
  53. {
  54.    char *stack[40], **sp;       /* stack and stack pointer        */
  55.    char *i, *j, *limit;         /* scan and limit pointers        */
  56.    size_t thresh;               /* size of T elements in bytes    */
  57.    char *base;                  /* base pointer as char *         */
  58.  
  59. #ifdef   SWAP_INTS
  60.    size_t width;                /* width of array element         */
  61.    void (*swap_func)(char *, char *, size_t); /* swap func pointer*/
  62.  
  63.    width = size;                /* save size for swap routine     */
  64.    swap_func = swap_chars;      /* choose swap function           */
  65.    if ( size % sizeof(int) == 0 ) {   /* size is multiple of ints */
  66.       width /= sizeof(int);           /* set width in ints        */
  67.       swap_func = swap_ints;          /* use int swap function    */
  68.    }
  69. #endif
  70.  
  71.    base = (char *)basep;        /* set up char * base pointer     */
  72.    thresh = T * size;           /* init threshold                 */
  73.    sp = stack;                  /* init stack pointer             */
  74.    limit = base + nelems * size;/* pointer past end of array      */
  75.    for ( ;; ) {                 /* repeat until break...          */
  76.       if ( limit - base > thresh ) {  /* if more than T elements  */
  77.                                       /*   swap base with middle  */
  78.          SWAP((((limit-base)/size)/2)*size+base, base);
  79.          i = base + size;             /* i scans left to right    */
  80.          j = limit - size;            /* j scans right to left    */
  81.          if ( COMP(i, j) > 0 )        /* Sedgewick's              */
  82.             SWAP(i, j);               /*    three-element sort    */
  83.          if ( COMP(base, j) > 0 )     /*        sets things up    */
  84.             SWAP(base, j);            /*            so that       */
  85.          if ( COMP(i, base) > 0 )     /*      *i <= *base <= *j   */
  86.             SWAP(i, base);            /* *base is pivot element   */
  87.          for ( ;; ) {                 /* loop until break         */
  88.             do                        /* move i right             */
  89.                i += size;             /*        until *i >= pivot */
  90.             while ( COMP(i, base) < 0 );
  91.             do                        /* move j left              */
  92.                j -= size;             /*        until *j <= pivot */
  93.             while ( COMP(j, base) > 0 );
  94.             if ( i > j )              /* if pointers crossed      */
  95.                break;                 /*     break loop           */
  96.             SWAP(i, j);       /* else swap elements, keep scanning*/
  97.          }
  98.          SWAP(base, j);         /* move pivot into correct place  */
  99.          if ( j - base > limit - i ) {  /* if left subfile larger */
  100.             sp[0] = base;             /* stack left subfile base  */
  101.             sp[1] = j;                /*    and limit             */
  102.             base = i;                 /* sort the right subfile   */
  103.          } else {                     /* else right subfile larger*/
  104.             sp[0] = i;                /* stack right subfile base */
  105.             sp[1] = limit;            /*    and limit             */
  106.             limit = j;                /* sort the left subfile    */
  107.          }
  108.          sp += 2;                     /* increment stack pointer  */
  109.       } else {      /* else subfile is small, use insertion sort  */
  110.          for ( j = base, i = j+size; i < limit; j = i, i += size )
  111.             for ( ; COMP(j, j+size) > 0; j -= size ) {
  112.                SWAP(j, j+size);
  113.                if ( j == base )
  114.                   break;
  115.             }
  116.          if ( sp != stack ) {         /* if any entries on stack  */
  117.             sp -= 2;                  /* pop the base and limit   */
  118.             base = sp[0];
  119.             limit = sp[1];
  120.          } else                       /* else stack empty, done   */
  121.             break;
  122.       }
  123.    }
  124. }
  125.  
  126. /*
  127. **  swap nbytes between a and b
  128. */
  129.  
  130. static void swap_chars(char *a, char *b, size_t nbytes)
  131. {
  132.    char tmp;
  133.    do {
  134.       tmp = *a; *a++ = *b; *b++ = tmp;
  135.    } while ( --nbytes );
  136. }
  137.  
  138. #ifdef   SWAP_INTS
  139.  
  140. /*
  141. **  swap nints between a and b
  142. */
  143.  
  144. static void swap_ints(char *ap, char *bp, size_t nints)
  145. {
  146.    int *a = (int *)ap, *b = (int *)bp;
  147.    int tmp;
  148.    do {
  149.       tmp = *a; *a++ = *b; *b++ = tmp;
  150.    } while ( --nints );
  151. }
  152.  
  153. #endif
  154.